DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2023.3

Optimal Algorithms for Learning Quantum Phase States

Authors: Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract

We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2ⁿ basis vectors x with amplitudes proportional to (-1)^{f(x)}, where f is a degree-d Boolean polynomial over n variables. We show that the sample complexity of learning an unknown degree-d phase state is Θ(n^d) if we allow separable measurements and Θ(n^{d-1}) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime poly(n) (for constant d) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli X and Z bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when f has sparsity-s, degree-d in its 𝔽₂ representation (with sample complexity O(2^d sn)), f has Fourier-degree-t (with sample complexity O(2^{2t})), and learning quadratic phase states with ε-global depolarizing noise (with sample complexity O(n^{1+ε})). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.

Cite as

Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2023.3,
  author =	{Arunachalam, Srinivasan and Bravyi, Sergey and Dutt, Arkopal and Yoder, Theodore J.},
  title =	{{Optimal Algorithms for Learning Quantum Phase States}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.3},
  URN =		{urn:nbn:de:0030-drops-183139},
  doi =		{10.4230/LIPIcs.TQC.2023.3},
  annote =	{Keywords: Tomography, binary phase states, generalized phase states, IQP circuits}
}

Search Results

Documents authored by Yoder, Theodore J.

Optimal Algorithms for Learning Quantum Phase States

Abstract

Cite as

Thanks for your feedback!

Could not send message